LeetCode 20. Valid Parentheses (Easy)

題目連結:

https://leetcode.com/problems/valid-parentheses/

解題思路

• 題目條件: 字串內只會有 '()[]{}'，不會有其他值
• Stack 堆疊

Stack (堆疊) 的特性

• 先進後出(First In, Last Out) 等於 後進先出(Last In, First Out)
• push : 將元素加到 stack 裡面
• pop : 從 stack 中把最後一個元素移除

解法

function isValid(s: string): boolean {
  const stack = [];
  const bracketsMap = {
    "(": ")",
    "[": "]",
    "{": "}",
  };

  for (let i = 0; i < s.length; i++) {
    const current = s[i];
    if (current in bracketsMap) {
      stack.push(current);
    } else {
      const lastOpenBracket = stack.pop();
      if (bracketsMap[lastOpenBracket] !== current) {
        return false;
      }
    }
  }
  return stack.length === 0;
}

Complexity :

• Time: O(n)， n 是輸入字符串 s 的長度
• Space: O(n)

解釋:

1. 建立一個空陣列來模擬 stack，用來儲存開括號
2. 建立一個名為 bracketsMap 的物件，來檢查括號之間是否互相搭配
3. 用 for loop遍歷整個字串 s
4. 先確認 current 是否是開括號，因為如果不是的話括號永遠不會閉合。如果是的話在加到 stack 裡面。
5. 如果字符 current 不是 bracketsMap 中的鍵，則表示是一個關閉括號。在這種情況下，需要檢查它是否與堆疊中的最後一個開括號匹配。 stack.pop() 會移除並回傳陣列的最後一個元素，並且檢查是否與 current 是相對應的關閉括號。如果不相符，則返回 false，表示括號不匹配。
6. 如果 stack.length 不是 0，代表有括號沒有被配對到，會返回 false。如果都有配對到 stack.length 會是 0 ，則回傳 true 。